#include "dys_dedup.h"

void calcHash(char *output, const char *input) {
    memcpy(output, input, FPSZ);
    ++*output;
}

bn_t allocate_new_data_block(void) {
    return datacnt++;
}

bn_t allocate_new_meta_block(void) {
    return metacnt++;
}

static inline void new_curr_block(void) {
    metadata_curr = Kzalloc(sizeof(struct metadata_blk));
    metadata_curr->blockid = allocate_new_meta_block();
    metadata_curr->valid_num = 0;
    ref_curr = Kzalloc(sizeof(struct refcount_blk_s));
    ref_curr->block_id = metadata_curr->blockid;
    return;
}

/**
 * 这个是read_dedup用来获取entry的函数
 * 查找顺序:
 * 1. metadata_curr
 * 2. 遍历metahead LRU链表, 找到则换到LRU第一个
 * 3. 直接根据blockid, 从磁盘中读取对应块, 直接替换LRU最后一个
 * 并没有将ref的链表也LRU, 因为ref代表写, meta代表读, 这样可以同时兼顾读写密集的应用
 * TODO: 可以试一试换入换出时到底要不要放到头部
*/
static inline struct metadata_entry* find_meta_entry(bn_t entryid) {
    struct metadata_blk *metablk;
    struct list_head list_backup;
    ssize_t readcnt;
    bn_t bindex = BINDEX(entryid), boffset = BOFFSET(entryid);
    // 头块
    if (bindex == metadata_curr->blockid) {
        return metadata_curr->entries + boffset;
    }
    DBG(DBG_LRU_LIST, "curr not found\n");

    // LRU in Memory
    list_for_each_entry(metablk, &metahead, list_head) {
        if (metablk->blockid == bindex) {
            list_move(&metablk->list_head, &metahead);
            return metablk->entries + boffset;
        }
    }
    DBG(DBG_LRU_LIST, "LRU in mem not found\n");

    // in disk
    // 把最后一个写到磁盘里面
    metablk = list_last_entry(&metahead, struct metadata_blk, list_head);
    bWriteMeta(metablk->blockid, (char *)metablk);
    memcpy(&list_backup, &metablk->list_head, sizeof(struct list_head));
    
    // 直接读回来, 并不是放到LRU头, 防止零散的读取操作
    // list_move(&metablk->list_head, &metahead);
    readcnt = bReadMeta(bindex, (char *)metablk);
    /**
     * 注意保留内存中的list_head
     * TODO: 考虑不将list_head写入磁盘
    */
    memcpy(&metablk->list_head, &list_backup, sizeof(struct list_head));
    if (readcnt == sizeof(struct metadata_blk)) {
        // BUGS: 这里实际上假定了metadata_blk和BLKSZ是一样大的
        return metablk->entries + boffset;
    }

    pr_alert("metablk %d not found, readcnt: %ld\n", bindex, readcnt);
    return NULL;
}

/**
 * 相当于find_ref_entry, 只是多了一个加减的功能
*/
void change_ref(bn_t entryid, bool add) {
    struct refcount_blk_s *refblk;
    bn_t bindex = BINDEX(entryid), boffset = BOFFSET(entryid);
    // 找对应bindex的ref块
    if (bindex == ref_curr->block_id) {
        // curr
        if (add) {
            ++ref_curr->ref[boffset];
        } else {
            --ref_curr->ref[boffset];
        }

        return;
    } else {
        // lru
        list_for_each_entry(refblk, &refhead, list_head) {
            if (refblk->block_id != bindex) continue;

            if (add) {
                ++refblk->ref[boffset];
                // 只在加的时候进行LRU
                list_move(&refblk->list_head, &refhead);
            } else {
                --refblk->ref[boffset];
            }

            return;
        }
    }
    // ref block不写入磁盘
    pr_alert("ref entry %d not found", entryid);
    return;
}

void traceback(void) {
    struct metadata_blk *metablk;
    struct metadata_entry *entry;
    int i;
    
    pr_alert("========== traceback ==========\n");
    pr_alert("datacnt: %d, metacnt: %d\n", datacnt, metacnt);

    // metadata_blk
    metablk = metadata_curr;
    pr_alert("metadata_curr => blockid: %d, valid_num: %d", metablk->blockid, metablk->valid_num);
    for (i = 0; i < ENTRY_PER_BLK; i++) {
        entry = metablk->entries + i;
        pr_alert("    entry%d => fp: %x, pbn: %d", i, *(uint32_t*)entry->fp, entry->pbn);
    }

    pr_alert("empty: %d", list_empty(&metahead));

    list_for_each_entry(metablk, &metahead, list_head) {
        pr_alert("metadata_blk => blockid: %d, valid_num: %d", metablk->blockid, metablk->valid_num);
        for (i = 0; i < ENTRY_PER_BLK; i++) {
            entry = metablk->entries + i;
            pr_alert("    entry%d => fp: %x, pbn: %d", i, *(uint32_t*)entry->fp, entry->pbn);
        }
    }
}

/**
 * 将metadata_curr放到LRU链上
 * OPTM: 由于new_curr_block内申请了新的block, 故这里没有使用find_meta_entry中的原位替换, 而是直接free
 * 实际上这里是先free再malloc, 所以没太大区别
*/
void expand_metablk(void) {
    struct metadata_blk *metablk;
    if (metablk_inMem >= metablk_keep) {
        metablk = list_last_entry(&metahead, struct metadata_blk, list_head);
        list_del(&metablk->list_head);
        bWriteMeta(metablk->blockid, (char *)metablk);
        Kfree(metablk);
        --metablk_inMem;
    }
    list_add(&metadata_curr->list_head, &metahead);
    list_add(&ref_curr->list_head, &refhead);
    new_curr_block();
    ++metablk_inMem;
    return;
}

int write_dedup(bn_t lbn, const char *content) {
    struct fp2PBN *f2p, *new_f2p;
    struct LBN2PBN *l2p, *new_l2p;
    // struct refcount_blk_s *refblk, *new_refblk;
    // struct metadata_blk *metablk, *new_metablk;
    struct metadata_entry *entry;
    // bn_t bindex, boffset; // 块序号 块内偏移
    uint32_t valid_num, entryid; // _, 指示此content的entryid

    // calc hash
    char *fp = Kzalloc(FPSZ * sizeof(char));
    calcHash(fp, content);
    // pr_alert("fp");
    // dumpArray(fp, FPSZ);

    // 根据fp查hash表
    f2p = rhashtable_lookup_fast(&f2p_rht, fp, f2p_params);
    if (f2p) {
        DBG(DBG_WRITE_DEDUP, "add ref. entryid: %d", f2p->entryid);
        // add ref
        change_ref(f2p->entryid, true);
        entryid = f2p->entryid;
    } else {
        DBG(DBG_WRITE_DEDUP, "allocate a new entry");
        // allocate a new entry

        if (metadata_curr->valid_num == ENTRY_PER_BLK) {
            // curr_block 已满, 需要重新申请新的block
            expand_metablk();
        }
        valid_num = metadata_curr->valid_num++;

        // 设置新的entry, ref, 并将内容写入磁盘
        entry = metadata_curr->entries + valid_num;
        memcpy(entry->fp, fp, FPSZ);
        entry->pbn = allocate_new_data_block();
        ref_curr->ref[valid_num] = 1;
        bWriteDedup(entry->pbn, content);

        // add to f2p hashmap
        entryid = GEN_ENTRYID(metadata_curr->blockid, valid_num);
        DBG(DBG_WRITE_DEDUP, "entryid: %x, %d, %d", entryid, metadata_curr->blockid, valid_num);

        new_f2p = Kzalloc(sizeof(struct fp2PBN));
        new_f2p->entryid = entryid;
        memcpy(new_f2p->fp, fp, FPSZ);
        rhashtable_insert_fast(&f2p_rht, &new_f2p->node, f2p_params);
    }
    
    // 根据lbn查hash表
    new_l2p = Kzalloc(sizeof(struct LBN2PBN));
    new_l2p->entryid = entryid;
    new_l2p->lbn = lbn;

    l2p = rhashtable_lookup_fast(&l2p_rht, &lbn, l2p_params);
    if (l2p) {
        rhashtable_replace_fast(&l2p_rht, &l2p->node, &new_l2p->node, l2p_params);
        // 如果是修改, 需要减引用
        change_ref(l2p->entryid, false);
    } else {
        rhashtable_insert_fast(&l2p_rht, &new_l2p->node, l2p_params);
    }

    Kfree(fp);
    return 0;
}

int read_dedup(bn_t lbn, char *content) {
    struct LBN2PBN *l2p;
    struct metadata_entry *entry;
    int ret;
    // 根据lbn查hash表
    l2p = rhashtable_lookup_fast(&l2p_rht, &lbn, l2p_params);
    if (!l2p) {
        // 这个是用户查询问题, 不是特别严重, 故只需返回0
        // pr_alert("lbn %d not found l2p\n", lbn);
        rDedupFail++;
        return 0;
    }
    DBG(DBG_READ_DEDUP, "l2p->entryid: %d\n", l2p->entryid);

    // 获取entry
    entry = find_meta_entry(l2p->entryid);

    // 搞到entry 读取数据
    if (!entry) {
        // 这个是元数据管理出现错误, 比较严重, 故需要返回-1
        pr_alert("metadata entry %d not found entry", l2p->entryid);
        return -1;
    }

    // 如果读不出来, 同样会返回0
    DBG(DBG_READ_DEDUP, "entry->pbn: %d\n", entry->pbn);
    ret = bReadDedup(entry->pbn, content);  // 后面还有一句, 不能直接 return bReadDedup(entry->pbn, content);
    return ret;
}

/**
 * BUGS: 这里的lbn不能使用32位的类型, 因为blkparse里会有超出32位的lbn
 * read_dedup因为是从头开始分配, 所以不会超
 * 但是bReadSimple是稀疏文件, 在乘上4096之后会超
*/
inline int read_both(unsigned long lbn, char *buf1, char *buf2) {
    ssize_t ret1, ret2;
    memset(buf1, 0, BLKSZ);
    memset(buf2, 0, BLKSZ);
    ret1 = bReadSimple(lbn, buf1);
    ret2 = read_dedup(lbn, buf2);
    DBG(DBG_READ_DEDUP, "ret1: %ld, ret2: %ld", ret1, ret2);

    if (!ret2 && !memcmp(buf1, buf2, BLKSZ)) {
        // 读取稀疏文件时, 如果遇到空洞, kernel_read仍然返回正常大小, 但是内容全是0
        // 如果read_dedup读不出来, 那么buf2就全是0, 这是将buf1与buf2比较, 判断其是否全为0
        rFail++;
        return 0;
    }

    if(memcmp(buf1, buf2, BLKSZ)) {
        pr_alert("test failed");
        pr_alert("lbn: %lu, buf1: %s, buf2: %s", (unsigned long)(lbn), buf1, buf2);
        return -1;
    }
    return 0;
}

#define MD5_STEP 256 // 哈希读取步长
#define MD5_READ_SZ FPSZ // 每次传过去的大小, 设置成FPSZ防止哈希碰撞
static inline int runTest(void) {
    struct file *fp;
    char *buf, *buf1, *buf2;
    int lineCnt = 0, opsCnt = 0, i;

    char *rdBuf, *md5Buf, *pLine;

    // blkparse
    unsigned long ts;
    unsigned long pid;
    char          pname[128];
    unsigned long lba;
    unsigned long blks;
    char          rw;
    int           major, minor;
    char          md5[MD5_READ_SZ + 1];

    // init
    buf  = Kzalloc(sizeof(char) * (BLKSZ + 1));
    buf1 = Kzalloc(sizeof(char) * (BLKSZ + 1));
    buf2 = Kzalloc(sizeof(char) * (BLKSZ + 1));

    const int rdBufSize = 1024 * 33;
    rdBuf = Kzalloc(rdBufSize);
    md5Buf = Kzalloc(rdBufSize);

    fp = filp_open(src, O_RDONLY, 0);
    if (IS_ERR(fp)) {
        pr_alert("Failed to open blkparse file\n");
        return PTR_ERR(fp);
    }

    // readlines
    fill_buffer(rdBuf, rdBufSize, fp);
    while ((pLine = kernel_readline_buffered(rdBuf, rdBufSize, fp)) != NULL) {
        lineCnt++;
        memset(pname, 0, 128);
        memset(md5, 0, MD5_READ_SZ + 1);

        sscanf(pLine, "%lu %lu %s %lu %lu %c %d %d %s", &ts, &pid, pname, &lba, &blks, &rw, &major, &minor, md5Buf);
        lba >>= 3;
        for (i = 0; i < blks / 8; i++) {
            opsCnt++;
            if (rw == 'W') {
                memcpy(md5, md5Buf + MD5_STEP * i, MD5_READ_SZ);
                writeBoth(lba + i, md5)
            } else if (rw == 'R') {
                if (read_both(lba + i, buf1, buf2)) goto rderr;
            } else {
                pr_alert("not RW operation\n");
            }
        }
        // if (lineCnt >= 5) break;
    }
    /*
    while(kernel_readline(buf, BLKSZ, fp) > 0) {
        line++;
        // memset(blk, 0, BLK_SIZE);
        memset(pname, 0, 128);
        memset(md5, 0, 256);

        sscanf(buf, "%lu %lu %s %lu %lu %c %d %d %s", &ts, &pid, pname, &lba, &blks, &rw, &major, &minor, md5);
        if (rw == 'W') {
            writeBoth(lba, md5)
        } else if (rw == 'R') {
            readBoth(lba)
        } else {
            pr_alert("not RW operation\n");
        }
    }
    */

    pr_alert("all %d lines %d ops test passed\n", lineCnt, opsCnt);
    goto exit;

rderr:
    pr_alert("line: %d", lineCnt);
    DBG_VALID_LIST[DBG_READ_DEDUP]=1;
    read_both(lba, buf1, buf2);
    traceback();

exit:
    filp_close(fp, NULL);
    Kfree(buf);
    Kfree(buf1);
    Kfree(buf2);
    Kfree(rdBuf);
    Kfree(md5Buf);
    return 0;
}

static int fs_init(void)
{
    int ret;
    struct refcount_blk_s *refblk, *ref_tmp;
    struct metadata_blk *metablk, *meta_tmp;

    pr_alert("========================================\n");

    init_DBG();
    init_massiveRW();

    // 初始化哈希表
    ret = rhashtable_init(&l2p_rht, &l2p_params);
    if (ret == -EINVAL){
        return -1;
    }
    ret = rhashtable_init(&f2p_rht, &f2p_params);
    if (ret == -EINVAL){
        return -1;
    }

    metablk_inMem = 0;
    datacnt = 0;
    metacnt = 0;
    new_curr_block();

    runTest();

// err_exit:
    rhashtable_free_and_destroy_m(&l2p_rht)
    rhashtable_free_and_destroy_m(&f2p_rht)
    Kfree(metadata_curr);
    Kfree(ref_curr);
    
	list_for_each_entry_safe(metablk, meta_tmp, &metahead, list_head){
		list_del(&(metablk->list_head));
		Kfree(metablk);
	}
	list_for_each_entry_safe(refblk, ref_tmp, &refhead, list_head){
		list_del(&refblk->list_head);
		Kfree(refblk);
	}

    end_massiveRW();
    pr_alert("rSimple: %d, wSimple: %d, rDedup: %d, wDedup: %d, rMeta: %d, wMeta: %d\n", rSimple, wSimple, rDedup, wDedup, rMeta, wMeta);
    pr_alert("rDedupFail: %d, rFail: %d\n", rDedupFail, rFail);
    return 0;
}

static void fs_exit(void)
{
    // split_all_data_file();
    printk(KERN_ALERT "Goodbye, cruel world\n");
}

module_param(src, charp, S_IRUSR);

module_init(fs_init);
module_exit(fs_exit);

MODULE_AUTHOR("cscn");
MODULE_DESCRIPTION("Flash Friendly File System");
MODULE_LICENSE("GPL");